'''
Created on Mar 11, 2015

@author: root
'''

import ctypes
import os
from random import randint
import time


LIB_PATH = r'./algo_c'
sort_lib_path = os.path.join(LIB_PATH, 'libsort.so')

def bubble_sort_in(l):
    for i in range(len(l)):
        for j in range(len(l) - 1, i, -1):
            if l[j] < l[j - 1]:
                l[j], l[j - 1] = l[j - 1], l[j]
    return l

def bubble_sort_de(l):
    for i in range(len(l)):
        for j in range(i + 1, len(l)):
            if l[i] < l[j]:
                l[i], l[j] = l[j], l[i]
    return l

def bubble_sort_in_improvement(l):
    """
    with a flag after very loop, we can stop privor if we find there is no exchange any more
    """
    for i in range(len(l)):
        exchange_flag = True
        for j in range(len(l) - 1, i, -1):
            #print i, j, l[j - 1], l[j]
            if l[j] < l[j - 1]:
                l[j], l[j - 1] = l[j - 1], l[j]
            #    print l
                exchange_flag = False
        if exchange_flag:
            print 'final:', i
            break
    return l

def bubble_sort(l, order = 'in'): 
    #return {'in': bubble_sort_in(l), 'de': bubble_sort_de(l)}[order]
    return {'in': bubble_sort_in, 'de': bubble_sort_de}[order](l)


def quick_sort_partion(l, low, high):
    """
    This function will return the pivot, meanwhile,
    it will make sure all the small numbers are on the left of the pivot while all the bigger numbers are on the right of the pivot
    """
    if high - low == 1: # if low is close near high, then we just choose low as the pivo
        pivo = low
    else: # get the index of the middle value in l[low], l[(low + high)/2] and l[high]
        pivo = sorted({low: l[low], (low + high)/2: l[(low + high)/2], high: l[high]}.items(), key = lambda d:d[1])[1][0]
    if pivo > low: # change the l[pivo] and l[low]
        l[low], l[pivo] = l[pivo], l[low]
    while low < high:
        while low < high and l[low] <= l[high]: # check from the right to left, means starting from high
            high -= 1
        if low < high: # means, found a l[high] < l[pivo]
            l[low], l[high] = l[high], l[low] # now ,l[low] is the value of l[high], and l[high] is l[pivo]
            low += 1
        while low < high and l[low] <= l[high]: # from left to right,
            low += 1
        if low < high: # means found a l[low] > l[pivo]
            l[low], l[high] = l[high], l[low] # now, l[high] is the value of l[low], and l[low] is l[pivo]
            high -= 1
    #print l
    #print low
    return  low

def quick_sort(l, low, high):
    """
    """
    if low < high:
        pivo = quick_sort_partion(l, low, high)
        quick_sort(l, low, pivo - 1)
        quick_sort(l, pivo + 1, high)

def insert_sort_in(l):
    for i in range(1, len(l)):
        temp = l[i]
        hit = False 
        for j in range(i-1, -1, -1):
            if temp >= l[j]:
                l[j+1] = temp
                hit = True
                break
            l[j+1] = l[j]
        if not hit:
            l[0] = temp
    return l

def insert_sort_de_sentinel(l):
    l.insert(0, 0)
    for i in range(2, len(l)):
        if l[i] < l[i-1]:
            l[0] = l[i]
            j = i - 1
            while l[0] < l[j]:
                l[j+1] = l[j]
                j -= 1
            l[j+1] = l[0]
    return l[1:]

def insert_sort(l, order = 'in'):
    return {'in': insert_sort_in, 'de': insert_sort_de_sentinel}[order](l)

def shell_pass(l, d):
    """"
    There is no sentinel for this functon
    """
    for i in range(d+1, len(l), d): # step should be d or 1, both work, but 1 should be better at performance.
        if l[i] < l[i-d]:
            l[0] = l[i]
            j = i-d
            while j > 0 and l[0]<l[j]:
                l[j+d] = l[j]
                j -= d
            l[j+d] = l[0]
            
def shell_pass_with_sentinel(l, d): 
    """
    How to set the sentinal????
    """
    for i in range(d+1, len(l)):
        if l[i] < l[i-d]:
            l[0] = l[d]
            l[d] = l[i] 
            j = i-d
            while l[d] < l[j]:
                l[j+d] = l[j]
                j -= d
            l[j+d] = l[d]
            l[d] = l[0]

def shell_sort(l, with_sentinel = False):
    """
    shell insert sort
    """
    l.insert(0, 0)
    #increment = 7
    #while increment > 1:
    if not with_sentinel:
        for increment in [7, 3, 1]: # here, we can just indicate the increment seq rather than generate dynamically
            shell_pass(l, increment)
        #incrment = increment/3 + 1
    else:
        for increment in [7, 3, 1]:
            shell_pass_with_sentinel(l, increment)

    return l[1:]

def straight_selection_sort(l):
    """
    straight selection sort also need to swap 2 numbers
    """
    for i in range(len(l)):
        k = i
        for j in range(i+1, len(l)):
            if l[k] > l[j]:
                k = j
        if k != i:
            l[i], l[k] = l[k], l[i]

def build_heap(l):
    """
    build a heap with the list
    """
    # the 1st stupid approach. 
    # this approach can not guarantee this array is a bin tree
    #for i in range((len(l)-1)/2, -1, -1):
    #    if i*2+1 < len(l) and l[i] < l[i*2+1]:
    #        l[i], l[2*i+1] = l[2*i+1], l[i]
    #    if i*2+2 < len(l) and l[i] < l[i*2+2]:
    #        l[i], l[2*i+2] = l[2*i+2], l[i]

    # the 2nd is the correct
    for i in range((len(l)-1)/2, -1, -1):
        adjust_heap(l, i, len(l)-1)

def adjust_heap(l, i, d):
    """
    adjust the heap
    l is the list
    i is the index from which note we will adjust the heap
    d is the index on which we will stop the adjust
    
    
    This is also the operation of heap deletion 
    the 1st key will be always deleted from the heap, and then, the last one will be put to the location of array[0]
    then, the adjust will be executed.
    """
    # the most stupid can be like this:
    #for i in range(d+1):
    #    if i*2+1 < d+1 and l[i] < l[i*2+1]:
    #        l[i], l[2*i+1] = l[2*i+1], l[i]
    #    if i*2+2 < d+1 and l[i] < l[i*2+2]:
    #        l[i], l[2*i+2] = l[2*i+2], l[i]
    tmp = l[i]
    j = 2*i+1
    while j < d+1:
        if j+1<d+1 and l[j]<l[j+1]:
            j += 1
        if tmp >= l[j]:
            break
        l[(j-1)/2] = l[j]
        j = 2*j+1 
    l[(j-1)/2] = tmp

def heap_sort(l):    
    """
    first build the heap with the list;
    then change the key with the l[0] and l[n-1]
    and adjust l[0...n-2]
    and change the key with l[0] and l[n-2]
    ....
    """
    build_heap(l)
    for i in range(len(l)-1, -1, -1):
        l[i], l[0] = l[0], l[i]
        adjust_heap(l, 0, i-1)
 
#####
#
# merge sort down to top
#
#####

def merge(in_list, out, low, m, high):
    i = low
    j = m+1 
    p = low
    while i<=m and j<=high:
        if in_list[i] <= in_list[j]:
            out[p] = in_list[i]
            i += 1
        else:
            out[p] = in_list[j]
            j += 1
        p += 1
    while i<=m:
        out[p] = in_list[i]
        i += 1
        p += 1
    while j<=high:
        out[p] = in_list[j]
        j += 1
        p += 1

def merge_pass(in_list, out, t):
    lenth = len(in_list)
    i = 0 
    while lenth-i>=2*t:
        merge(in_list, out, i, i+t-1, i+2*t-1)
        i = i+2*t
    if lenth-i>t:
        merge(in_list, out, i, i+t-1, lenth-1)
    else:
        while i<lenth:
            out[i] = in_list[i]
            i += 1

def merge_sort(in_list):
    t = 1
    out = [''] * len(in_list)
    while t < len(in_list):
        merge_pass(in_list, out, t)
        t *= 2
        merge_pass(out, in_list, t)
        t *= 2

######
#
# merge sort top to down, which is a recursion approach
#
#####

def merge2(in_list, low, mid, high):
    i = low
    j = mid+1
    tmp = []
    while i<=mid and j<=high:
        if in_list[i] > in_list[j]:
            tmp.append(in_list[j])
            j += 1
        else:
            tmp.append(in_list[i])
            i += 1
    while i<=mid:
        tmp.append(in_list[i])
        i += 1
    while j<=high:
        tmp.append(in_list[j])
        j += 1
    for i in range(low, high+1):
        in_list[i] = tmp[i-low]
        
def merge_sort_top_to_down(in_list, low, high):
    if low<high:
        mid = (low+high)/2
        merge_sort_top_to_down(in_list, low, mid)
        merge_sort_top_to_down(in_list, mid+1, high)
        merge2(in_list,low, mid, high)

def generate_list(n):
    #return [randint(0, n) for i in range(n)]
    l = [item for item in range(n/2)]
    l.extend([randint(n/2, n) for i in range(n/2)])
    #l = [item for item in range(n/2)]
    #l.extend([randint(n/2, n) for x in range(n/2, n)])
    return l

def generate_list2(n, max):
    return [randint(0, max) for i in range(n)]

def test_quick_sort(l):
    #l = generate_list(30)
    #print l
    #quick_sort_partion(l, 0, len(l) - 1)
    l = l[:]
    t0 = time.time()
    quick_sort(l, 0, len(l) - 1)
    t1 = time.time()
    print l
    print t1 - t0
    
def test_bubble_sort(l):
    #l = generate_list(10000)
    #l = [1,2,3,4,5,6,9,8,7]
    #l = [0, 1, 2, 3, 4, 7, 9, 5, 8, 10]
    #l = [0, 1, 2, 3, 4, 9, 8, 5, 6, 5]
    #l = generate_list(10000)
    l1 = l[:]
    l2 = l[:] # if don't do this, l will be changed by every sort
    t0 = time.time()
    print bubble_sort(l)
    t1 = time.time()
    print bubble_sort(l1, 'de')
    t2 = time.time()
    print bubble_sort_in_improvement(l2)
    t3 = time.time()

    print t1 - t0
    print t2 - t1
    print t3 - t2

def test_insert_sort(l):
    #l = [79, 26, 34, 15, 71, 17, 2, 21, 9, 81]
    sort = ctypes.CDLL(sort_lib_path)
    l1 = l[:]
    l2 = l[:]
    l3 = l[:]
    l4 = l[:]
    l4.insert(0, 0)
    l5 = (ctypes.c_int * len(l4))(*l4)
    t0 = time.time()
    print 'l1', insert_sort(l1)
    t1 = time.time()
    print 'l2', insert_sort(l2, 'de')
    t2 = time.time()
    print 'l3', shell_sort(l3)
    t3 = time.time()
    sort.shell_sort(l5, len(l5))
    t4 = time.time()
    print 'l5', list(l5)
    print t1-t0
    print t2-t1
    print t3-t2
    print t4-t3

def test_selection_sort(l):
    sort = ctypes.CDLL(sort_lib_path)
    l1 = l[:]
    l2 = l[:]
    l2.insert(0, 0)
    l3 = (ctypes.c_int * len(l2))(*l2)
    l4 = l[:]
    l5 = l[:]
    l5 = (ctypes.c_int * len(l5))(*l5)
    t0 = time.time()
    straight_selection_sort(l1)
    t1 = time.time()
    sort.straight_selection_sort(l3, len(l3))
    t2 = time.time()
    heap_sort(l4)
    t3 = time.time()
    sort.heap_sort(l5, len(l5))
    t4 = time.time()

    print l1
    print list(l3)
    print l4
    print list(l5)
    print t1 - t0
    print t2 - t1
    print t3 - t2
    print t4 - t3

def test_merge_sort(l):
    sort = ctypes.CDLL(sort_lib_path)
    l1 = l[:]
    l1 = (ctypes.c_int * len(l1))(*l1)
    l2 = l[:]
    l3 = l[:]
    l3 = (ctypes.c_int*len(l3))(*l1)
    l4 = l[:]
    t0 = time.time()
    sort.merge_sort(l1, len(l1))
    t1 = time.time()
    merge_sort(l2)
    t2 = time.time()
    sort.merge_sort_top_to_down(l3, 0, len(l3)-1)
    t3 = time.time()
    merge_sort_top_to_down(l4, 0, len(l4)-1) 
    t4 = time.time()
    
    print list(l1)
    print l2
    print list(l3)
    print l4
    print t1 - t0
    print t2 - t1
    print t3 - t1
    print t4 - t1

def test_sort():
    l = generate_list2(2000, 20)
    print l
    #test_bubble_sort(l)
    #test_quick_sort(l)
    #test_insert_sort(l)
    #test_selection_sort(l)
    test_merge_sort(l)

def main():
    test_sort()

   
    
if __name__ == '__main__':
    main()